Many computer graphics applications such as, for example, flight simulators, need to allow users to visualize, or fly over, terrains in real time. In order to accomplish this task, applications implement various systems, methods and processes generally known as terrain rendering.
These terrains may be represented by a combination of a geometry and a texture. The geometry is typically a triangular mesh detailing the surface of the terrain, while the texture provides the patterning or coloring appropriate to each triangle of the mesh. The texture, or texture map, for instance, may be a high-resolution satellite imagery digitized into texels. Such satellite images may, for instance, have 3 meter resolution so that the texture representing an area of 30 square kilometers may have as many as 100 million texels.
Large textures may have to be stored in a large texture database or other storage medium, which are cheaper than texture memory, but cannot be accessed as quickly by a graphics processing unit or GPU. The problem of increasing texture size, however, is further exacerbated in the case of mip-mapping, discussed in greater detail below, where multiple copies of a texture image at different resolutions are also stored. A mip-map consists of a high resolution texture pattern pre-filtered at progressively lower or coarser resolutions and stored in varying levels of detail (LOD) maps.
The process of combining, or binding, the appropriate region of the texture (which is two dimensional) to the appropriate triangle of the geometry mesh (which is three dimensional), and determining the color of the pixels to be projected onto a display device, such as a cathode ray tube (CRT) or liquid crystal diode (LCD) display screen, involves complex computation and is usually referred to as rendering, and, in the instance of terrain texture, terrain rendering. A texture is simply a two dimensional image, the size of which varies, that is applied through the process of binding to a three dimensional object to simulate its surface. Once the texture is applied to the three dimensional object, the object appears as though the texture has been “painted” on it.
Modern graphic computer workstations typically only allow the rendering and display of a few thousand textured triangles at real-time interactive rates. A major challenge for a real-time, geo-specific terrain rendering system involving a workstation computer with a “commodity” GPU, therefore, is dealing with the large amount of data that must be processed to cover a large terrain expanse using a texture that is based on high-resolution satellite imagery. Moreover, further exacerbating this challenge, the rendering architecture of the workstation computer must be able to utilize the graphics capabilities of the workstation in a way that allow real time rendering of geo-specific terrain in the most life-like way, i.e., with as few artifacts as possible, without interruption, and without overtaxing computer system resources.
A background of terrain rendering is now presented.
FIG. 1 is a schematic representation of a toroidal texture map 10 having an origin 12. The toroidal texture map 10 is called toroidal because edge 14 rolls over to edge 16, i.e., as the origin 12 is moved, the texels that are removed at edge 14 reappear at edge 16. Similarly edge 18 rolls over to edge 20. If the texture map 10 is visualized as having edges 14 and 16, and edges 18 and 20 joined, it forms a torus or toroid, hence the nomenclature.
A significant amount of the image processing required when using a high resolution texture in an interactive or real-time graphics display results from the fact that a single pixel of the display typically covers many texels of the high resolution texture.
FIG. 2A is a view of a portion of the toroidal texture map 10 in pixel space. This is the view of the texture as seen on the graphics display device, such as a computer monitor or other display, and the pixel 24 is square. FIG. 2B shows a view of the toroidal texture map 10 in texel space. A display pixel 24 is projected back onto the toroidal texture map 10 and covers several texels 22. To obtain the correct or most graphically accurate color to display on the display pixel 24, the effect of all the texels 22 influencing the pixel 24 should be integrated. It is, however, difficult to determine the precise influence of all the texels 22 near a particular pixel 24, and it is effectively computationally impossible to do so perfectly in real time. Simple filtering techniques, such as picking the texel 22 at the center of the pixel 24, usually result in severe aliasing of the image, i.e., the sampling causes artifacts such as, but not limited to, straight lines or edges becoming broken or jagged. Solving the problem of obtaining the correct pixel color to display is, therefore, often referred to as anti-aliasing the texture, of which there are known methods within the art.
A popular texture anti-aliasing method is “mip-mapping.” (“mip” stands for “multum in parvo,” which is Latin for “many things in a small space”—in this case, many texels (“many things”) projected to lie within a pixel (“small place”) of the display device). In mip-mapping, the high resolution texture is pre-filtered into a pyramid of smaller textures, or levels, each representing the texture at a lower resolution. As the pre-filtering is only done once off-line, more sophisticated, computationally expensive techniques can be used. These techniques include, but are not limited to, Gaussian, Lanczos or Kaiser filtering, with appropriate gamma correction to adjust the brightness of the texels.
The mip-map of a required region of the texture includes well corrected mip-map levels at a range of resolutions. In order to render a given fragment of a geometry, the rendering system first determines which of the mip-map levels is filtered to the appropriate resolution, i.e., which of the mip-map levels has texels that, given the required geometry, will come closest to appearing as a single pixel on the display screen. Such an approach is usually termed a multiple static Level-of-Detail (SLOD) solution.
In a typical real time terrain rendering application, such as an aircraft flight simulation, the observer typically views the terrain at an oblique angle. The nearby terrain is, therefore, seen at a significantly higher resolution than the distant terrain, near the horizon. Using a SLOD solution, a displayed image will have a number of steps as the system switches from using texels from one mip-map level to another mip-map level. These steps need to be blurred out using alpha-blending or some other smoothing effect.
Implementing a large texture mip-map requires a significant amount of memory. One way to reduce the memory requirement, however, is to use a “clip-map.” A clip-map is a partial mip-map in which each level has been clipped to a specified size. Clip-maps have been described in, for instance, U.S. Pat. No. 7,012,614 entitled “Texture Roaming via Dimension Elevation” issued to Chalfin, et al., on Mar. 14, 2006, the contents of which are hereby incorporated by reference, and Christopher C. Tanner, et al., The Clipmap: A Virtual Mipmap, SGI paper, Computer Graphics Proceedings Annual Conference Series, 1998, pp 151-158, the contents of which are also hereby incorporated by reference. The clip-map representing a subset of the complete mip-map may be transferred to, and stored in, graphics (texture) memory where it may be accessed more quickly than from the database or other storage. The standard full size mip-map may be stored in a database on a disk or other less expensive storage area.
FIG. 3 is an isometric view of a combined mip-map and clip-map 26. The mip-map of FIG. 3 has a mip-map level(0) 32. The clip-map portion of FIG. 3 has a clip-map level(0) 30 and a clip-map level(1) 34. The clip-map level(1) 34 is the mip-map level (2) 28 clipped to be the same size as clip-map level(0) 30. It should be noted that this labeling of levels used in this specification is in contrast to the labeling of levels used in OpenGL and common computer graphics in which the numbering for mip-maps typically has zero as the highest resolution and higher numbers for lower resolutions. The labeling of levels as described in this specification has the advantage of dealing or working more easily with texture libraries growing by the addition of higher resolution imagery.
Generally, the texel data in each level of the combined mip-map and clip-map 26 is referred to as a “tile,” which is further comprised of a collection of “sub-tiles,” thereby resulting in a “texture mosaic” at each such mip-map or clip-map level. As such, the combined mip-map and clip-map 26 can be thought of as a texture mosaic or set of sub-tiles made up of texel data corresponding to a source texture image filtered at different resolutions and clipped at a specified clip size.
FIG. 4A is a one dimensional representation of an exemplary combined mip-map and clip-map 26. In this example, the mip-map 38 has three levels. As seen from FIG. 4B, mip-map level 0 is a 3-by-3 array of pixels, mip-map level 1 is a 6-by-6 array of pixels and mip-map level 2 is a 12-by-12 array of pixels. The clip-map 36 has 5 levels, each of which is a 12-by-12 array of pixels. FIG. 4C is a one dimensional representation of the region of real space covered by each level of the combined clip-map and mip-map 26.
Each level of the mip-map region 42 of the combined mip-map and clip-map 26 covers the same extent of real space, but with each increasing level having a progressively higher resolution, and therefore, requiring more pixels to represent the region. Each increasing level of the clip-map region 40, in contrast, covers a progressively smaller extent of real space, but each at a progressively higher resolution, so that a constant number of pixels is required for all the levels of the clip-map region 40.
For terrain rendering applications supported by clip-mapping, texel data is drawn from an appropriate level of detail within a clip-map cached in either main or graphics (texture) memory. The clip-map is centered about a clip center, which can be an arbitrary texture space coordinate that defines the center of each clip map level. Often the clip center is associated with an eye point in a graphical application. In this way, texture at the finest resolution can be provided near an eye point and coarse texture can be drawn from levels further away from the eye point.
As the user flies over the terrain in a flight simulation application, and the eye-point of a geo-specific terrain rendering system changes, the clip-map levels cached in main and/or graphics memory will require updating from the database. The updating may be done by loading into memory the applicable clip-map terrain imagery in small blocks of texels previously referred to herein as sub-tiles. As noted, each level or tile of the texture is sometimes referred to as a mosaic texture because it is composed of a collection of such sub-tiles. The updating may be performed using toroidal addressing of the sub-tiles of each level of the clip-map. Toroidal addressing is described at length in the article, Christopher C. Tanner, et al., The Clipmap: A Virtual Mipmap, SGI paper, Computer Graphics Proceedings Annual Conference Series, 1998.
Although clip-mapping has advantages, its use to date has been limited to specialized hardware designed to support clip-mapping, such as the InfiniteReality Machine graphics hardware available from SGI, a Delaware Corporation, or to methods such as the “extra-dimension clip-map,” as described in U.S. Pat. No. 7,012,614. Significantly, in both of these implementations of clip-mapping, all levels of the clip-map are updated simultaneously, which is wasteful of transfer bandwidth between the data-base containing the complete texture data-base and main system and graphics memory. Synchronous transfer of all clip-map levels, required in both of these prior implementations of clip-mapping, is also an inefficient use of graphics memory.
What is needed, therefore, is a system and method to implement clip-mapping using standard or commodity graphics hardware and in a way that makes efficient use of transfer bandwidth between a database storing the complete mip-map and the graphics (texture) memory of the graphics hardware.